The present invention relates to packet communication networks, and more particularly to parsing of packets transmitted over a communication network.
A packet communication network typically includes a number of network devices, such as switches, routers, traffic controllers and traffic shapers that transmit, reroute or manage the flow of packets across the network. Each packet, in addition to data, also includes a number of control fields disposed in the packet's header. Such fields includes, for example, the source and destination address of the packet as well as the kind of operation that is required to be performed on the data disposed in the packet. Packets are often formed to comply with multi-layer network protocols that govern the flow and management of the packets across the many layers of such networks.
At the transmitting end, each layer of the network adds an associated header to the packet as the packets moves down from a higher layer to a lower layer. At the receiving end, each layer retrieves the header associated with that layer, performs the operations instructed by the header and, subsequently, forwards the packet to a higher layer. Accordingly, instructions regarding how a packet is to be processed by each layer of a multi-layer network is disposed in an associated packet header.
A packet is often parsed by a protocol parser in accordance with a set of predefined network protocols and rules that, in aggregate, define the encapsulation structure of the packet. The protocol parser generates information regarding the protocol type at each network layer, identifies the boundary—in byte offset—of the layers, and extracts such information as address and control fields that are required for processing of the packets at each layer of the network.
A prior art method of parsing packets includes using protocol discrimination software. Such software typically analyzes the various control fields disposed in the packet to identify the protocol in accordance with which the packet is formed. Thereafter, the packet is parsed in accordance with the classification rules and policies that define the protocol. The protocol discrimination software often processes the control and/or data field of a packet on a layer-by-layer basis.
A Central Processing Unit (CPU) often deployed to execute the codes of a protocol discrimination software is required to operate at clock frequencies that are typically an order of magnitude higher than that at which data disposed in the packet is received. In view of the ever increasing need for network bandwidth, such CPUs must operate at even faster rates. Consequently, a protocol discrimination software adapted to be executed by a CPU is often not a cost-effective packet parser.
To provide Quality of Service (QoS) and fine grain traffic management, emerging networking applications require a packet parser to handle a large number of customized network policies. Such customized policies typically need to operate on fixed-length as well as variable-length data fields disposed in a multitude of layer-associated packet headers which may also have complex dependencies. Protocol discrimination software, however, is typically adapted to handle a limited number of relatively simple classification rules. Furthermore, disadvantageously, an end user often does not have access to the software source code and therefore is unable to modify the source code. Such modification may be necessary to enable the software to recognize and parse packets formed in accordance with network protocols and policies other than those for which the software is originally customized.
To overcome some of the disadvantages of software discrimination protocols, hardware-based fixed protocol identifiers have been developed. The hardware in such fixed protocol identifiers includes a state machine that sequences through a predefined sequence of states to recognize and process encapsulation protocols, such as Internet Protocol (IP), Virtual Local Area Network (VLAN), and Sub Network Access protocol (SNAP) encoded Logical Link Control (LLC). The state-machine disposed in a fixed protocol identifier, however, is hard-wired and thus may not be reprogrammed to recognize and process packet header fields other those for which the state machine is hard-wired.
A programmable field detector is another example of a hardware-based packet parser. A programmable field detector typically includes a state machine that may be programmed to process a small number of customized classification rules and network protocols. However, the state machine in such a programmable field detector has a very limited degree of programmability and thus may not be programmed to recognize and process relatively larger number of classification rules and network protocols.
Another conventional method for protocol parsing involves the use of decision trees. Packet parsers that use decision trees are deployed in network processors or classifier devices, such as those available from Solidum Systems, located at 1575 Carling Avenue, Ottawa, Ontario, KIZ 7M3, Canada, or Agere Systems, located at 555 Union Boulevard, Allentown, Pa. 18109. In accordance with such methods, the rules and policies of supported protocols are defined and mapped to a decision tree. Each internal node of a decision tree defines one or more comparison operations, each represented by a branch (i.e., arc) leading to another node. Each leaf node (i.e., end node) defines a parsing result associated with a protocol type. To parse a packet, a decision tree is analyzed from its root to a leaf on a node-by-node basis. At each internal node, one or more compare and branch operations are performed to determine the next node in the parsing process.
A conventional multi-layer network typically supports a number of protocol formats for each layer. A decision-tree representation for such multi-layer networks may require a subtree associated with a supported protocol format to be replicated once for the higher layer and once for each of a number of lower layers each leading to a leaf node. Since the number of leaf nodes is equal to the product of the number of supported protocols and the number of layers disposed in these protocols, the decision tree suffers from the explosion problem.
FIGS. 1A and 1B show the multitude of nodes and branches of a prior art decision tree 10 representing an IP over Ethernet protocol. The Ethernet layer is shown as supporting packet formats Ethernet V3.0 802.3 SNAP encoded LLC, Ethernet V3.0 802.1p VLAN tagged frames and 802.3 SNAP encoded LLC VLAN tagged frames. Because the parsing subtree for the IP header is replicated for each of these level 2 frame formats, the IP subtree is repeated for four times. The repeated IP subtrees 12, 14, 16 and 18 are respectively associated with Ethernet V3.0, 802.3 SNAP encoded LLC, Ethernet V3.0 802.1p VLAN tagged frames, and 802.3 SNAP encoded LLC VLAN tagged frames. As seen from FIGS. 1A and 1B, as the tree depth increases to support more complicated and deeper protocol formats, the size of the tree increases exponentially. Furthermore, as seen from prior art FIGS. 1A and 1B, there are no paths (i.e., branches) between any two nodes originating from the same node. For example, there is no path between nodes VLAN and LLC, both of which originate from node Ethertype. Therefore, if a packet includes SNAP encoded LLC VLAN tagged frame, because there is no path between VLAN and LLC nodes originating from node Ethertype, a second LLC node originating from VLAN node is included in decision tree 10.
When parsing packets formed in accordance with a multi-layer network, such as the seven layers associated with the Open Systems Interconnection (OSI) standard, the number of supported protocols may become large. Moreover, because of emerging network applications, many encapsulation protocols are being adapted to support recursive layering. For example, assume that an entity prefers to run an Layer 2 Tunneling Protocol (L2TP) tunnel for a Virtual Private Network (VPN) application across an Internet Protocol (IP) network—that is managed by an IP provider—then the L2TP tunnel is established between two of the entity's remote sites to carry across the Ethernet traffic. Therefore, the Layer Two traffic associated with the IP and the Layer One traffic associated with the Ethernet must be encapsulated in the L2TP layer. Therefore, the Ethernet and IP layers are recursive layers, as they appear once in Layers One and two, respectively, and again as they are encapsulated in the L2TP layer. To parse a packet adapted for such a network application using a decision-tree requires that Layers Two through Four be parsed twice, once after Layer One is parsed, and a second time after Layer Four is parsed.
As the number of recursive layers increases, any subtree representative of the protocol formats in a higher layer encapsulating a lower layer is replicated to include the end-to-end tree branches associated with the lower layer protocol. Hardware-based decision trees thus unnecessarily duplicate the compare and branch operations that are involved in parsing packets with recursive layers, and as such are inefficient. In other words, hardware-based decision trees are not easily scalable, are inefficient and are not adapted to meet the growing demand for supporting multi-layer, complex and recursive network protocol layers.